package com.njupt.graphTheory;


import java.util.ArrayList;
import java.util.List;

/**
 * @Author: wujiaming
 * @CreateTime: 2025/2/2 22:04
 * @Description: 207. 课程表
 * @Version: 1.0
 */


public class CanFinish_Dfs_207 {

    //判断是否合法（拓扑排序中是否存在回路）
    public boolean valid = true;



    /**
     * 基于邻接表的深度优先遍历，遍历的时候将节点放入集合中（不能出现回路），并同时计数
     *一般用一个二维的list来表示邻接表，list的下标来表示顶点，对应的表示该顶点的出度
     * @param numCourses
     * @param prerequisites
     * @return
     */
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<List<Integer>> graph = new ArrayList<List<Integer>>();
        int[] isVisited = new int[numCourses];
        //1、使用连接表创建图
        for (int i = 0; i < numCourses; i++) {
            graph.add(new ArrayList<>());
        }

        for (int[] array : prerequisites) {
            graph.get(array[1]).add(array[0]);
        }
        //2、拓扑排序
        //遍历每一个节点，对每一个节点进行深度优先遍历
        for (int i = 0; i < numCourses && valid; i++) {
            //对于每一个节点他没有遍历过，并且没有回路的情况下，对该节点进行深度优先遍历，进行拓扑排序
            if(isVisited[i] == 0){
                dfs(i,graph,isVisited);
            }
        }

        //2.1、深度优先遍历，当遍历到当前的节点u，如果u的所有相邻都完成了搜索，那么这些相邻的节点已经在栈中，回溯到当前节点u时已经完成了搜索

        return valid;
    }

    private void dfs(int u, List<List<Integer>> graph, int[] isVisited) {
        isVisited[u] = 1; //对向前节点i标记1，表示正在遍历中

        for (Integer v : graph.get(u)) {

            //下一个节点v，没有遍历的情况下，继续进行深度优先遍历
            if(isVisited[v] == 0){
                dfs(v,graph,isVisited);
                if(!valid){
                    return;
                }
            } else if (isVisited[v] == 1) {
                valid = false;
                return;
            }
        }
        isVisited[u] = 2; //标记状态为2，表示已经遍历完成
    }


    public static void main(String[] args) {
        int[][] prerequisites = {{1, 0}, {0, 1}};
//        int[][] prerequisites = {};
//        int[][] prerequisites = {{1,0}};
        CanFinish_Dfs_207 test = new CanFinish_Dfs_207();
        System.out.println(test.canFinish(2, prerequisites));
    }
}
